package com.ly.sort;


import java.util.Arrays;

public class MergeSort implements Sort{

    @Override
    public int[] sort(int[] arr) {
        if(arr.length < 2) return arr;
        int middle = arr.length / 2;
        int []left = Arrays.copyOfRange(arr, 0, middle);
        int []right = Arrays.copyOfRange(arr, middle, arr.length);
        return merge(sort(left), sort(right));
    }

    private int[] merge(int[] left, int[] right) {
        int arr[] = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < arr.length; index++) {
            if(i >= left.length){
                arr[index] = right[j++];
            }else if(j >= right.length){
                arr[index] = left[i++];
            }else if(left[i] > right[j]){
                arr[index] = right[j++];
            }else{
                arr[index] = left[i++];
            }
        }
        return arr;
    }



}
